import java.util.HashMap;
import java.util.Iterator;
import java.util.Random;

/**
 * Optimal optimizer, version that 
 * computes results for only those boxes that are non-empty. 
 * and does not keeping ContextDataCollections, thus using
 * less memory than SlowOptimal.  
 * @author Ed Hong
 *
 */
public class OptimalOptimizer extends AbstractOptimalOptimizer {

        public solutionInfo SOLUTIONZERO = new solutionInfo(null,0);
        
//        HashMap<ContextCharacteristicsBox, BitCounts> allCounts; // store of bitcounts for
            // each box. 
            
        class Solver implements Runnable {
            int threadID;
            double thresh;
            public Solver(int id, double threshold) {
                threadID = id;
                thresh = threshold;
            }
            public void run() {
                mysolve(cbstart, thresh, new ContextDataCollection(contextData), threadID);
            }
        }

    private static final int NUMBER_THREADS = 2;
    private Random[] randarr; 
    protected solutionInfo solve(ContextCharacteristicsBox cb, double threshold) {
    // create unique random object for each thread;
        randarr = new Random[NUMBER_THREADS];
        for (int i=0; i < NUMBER_THREADS; i++) {
            randarr[i] = new Random(i);
        }

    // create and start threads.
        for (int i=1; i < NUMBER_THREADS; i++) {
            final Thread t = new Thread(new Solver(i, threshold));
            t.start();
        }
/*        try {
            t.join();
        }
        catch (java.lang.InterruptedException e) {
            System.out.println("Caught InterruptedException:" + e); 
        }
        System.out.println("Join done");
        */
        randarr[0] = null; // use inorder for thread 0. 
        return mysolve(cb, threshold, contextData, 0);
    }
        // recursive dynprog solution. 
        // third argument is single ContextDataCollection implied by cb. 
            static int solvecount = 0;        
    static int earlystopcount = 0;
    static int maxsize_earlystop = 0;
    protected solutionInfo mysolve(ContextCharacteristicsBox cb, double threshold, ContextDataCollection cdc, 
        int threadID) {
            if (cb == null) return SOLUTIONZERO;
            if (DEBUG && ((++solvecount) % 100000 == 0)) {
              System.out.println("Thread#:"+ threadID + " " + cb + " numsol:" + allSol.size() + 
				 " solvecount:" + solvecount);
            }
            solutionInfo si;
            
            si = allSol.get(cb);
            if (si != null) 
                return si;
                
            if (cdc == null) {
                    throw new IllegalArgumentException();
            }
            
            // singleton box case. 
            if (cdc.size()==1) {
                BitCounts bc = cdc.getTotal();                
                si = new solutionInfo(null, 
                            Cost.adaptiveCostEstimate(bc));
                allSol.put(cb,si);
                return si; 
            }
	    // not worth exploring better solutions case:
	    else if (cdc.size() <=30 && cdc.computeOptimalAdaptiveCost() + threshold >= 
		     cdc.getTotal().getAdaptiveCost()) {
                BitCounts bc = cdc.getTotal();
                if (DEBUG && cdc.size() >= maxsize_earlystop) {
                    maxsize_earlystop = cdc.size();
		    System.out.println("maxsize_earlystop change, cdcsize=" + cdc.size() + 
				       " bitcount=" + bc + 
				       " earlystopcout=" + earlystopcount);
                    
                }
		if (DEBUG && ((++earlystopcount) % 10000 == 0)) {
		    System.out.println("stopping early, cdcsize=" + cdc.size() + 
				       " bitcount=" + bc + 
				       " earlystopcout=" + earlystopcount);
		}
                si = new solutionInfo(null, 
                            Cost.adaptiveCostEstimate(bc));
                allSol.put(cb,si);
                return si; 
		
	    }
            else  {
                // for each split criteria possible in cb
                // recursively solve
                // store overall min in allSol
                // return min. 

		Iterator<SplitCriteria> iter = cb.getSplitIterator(randarr[threadID]);
                solutionInfo best;
                solutionInfo sol1, sol2;
                best = new solutionInfo(null, Double.POSITIVE_INFINITY);
                int numcriteria = 0;
                ContextCharacteristicsBox[] boxes;
                boxes = new ContextCharacteristicsBox[2];
                boxes[0] = boxes[1] = null;
		while (iter.hasNext()) {
			SplitCriteria criteria = iter.next();
                        numcriteria++;
                        boxes = cb.split(criteria); // contains big boxes. 
//                        System.out.println("Box0: " + boxes[0]);
//                        System.out.println("Box1: " + boxes[1]);                       
                    //split data in cdc
                        ContextDataCollection[] cdcsplit = new ContextDataCollection[2];
                        cdcsplit[0] = new ContextDataCollection(cdc);
                        cdcsplit[1] = cdcsplit[0].split(criteria.getContextID(), criteria.getBucketID());
 
                    // make boxes smaller. 
                        boxes[0] = ContextCharacteristicsBox.findSmallestEnclosingBox(cdcsplit[0]);
                        boxes[1] = ContextCharacteristicsBox.findSmallestEnclosingBox(cdcsplit[1]);
 
                    // make recursive calls;  
                        sol1 = mysolve(boxes[0], threshold, cdcsplit[0], threadID);
                        // free memory
                        cdcsplit[0] = null;
                        sol2 = mysolve(boxes[1], threshold, cdcsplit[1], threadID);
                        double combined = sol1.cost + sol2.cost; 
                        if (combined < best.cost) {
                            best.cost = combined;
                            best.splitc = criteria;
                        }
                }
                if (numcriteria == 0) {
                    throw new IllegalArgumentException("mysolve:no valid split found");
                }
                // add split cost here                      
                best.cost += Cost.splitCost(numcriteria);
                
                // compare best so far with no splitting. 
                double newcost = Cost.adaptiveCostEstimate(cdc.getTotal());
                if (newcost <= best.cost) {
                    best.cost = newcost;
                    best.splitc = null;
                }
                  
                allSol.put(cb,best);
//                System.out.print(best + " " + newbc + " " );
                return best;
            }   
        }
        	
	public OptimalOptimizer(String ccdFile) {
		super(ccdFile);
 //               allData = new HashMap<ContextCharacteristicsBox, ContextDataCollection>( );
 //               ContextCharacteristicsBox cb = ContextCharacteristicsBox.getLargestBox();
 //               allData.put(cb,contextData);
                System.out.println("contextData: " + contextData.size() + " " + 
                                   contextData.getTotal());
	}

        static  int temp = 0;
        protected void buildOptimalTree(ContextCharacteristicsBox cb, 
                                ContextTreeNode currnode) {
                solutionInfo si = allSol.get(cb);        
                if (si.splitc != null) {
                    currnode.split(si.splitc);
                    ContextCharacteristicsBox[] boxes = cb.split(si.splitc);
/*                    //split data in cdc
                        ContextDataCollection[] cdcsplit = new ContextDataCollection[2];
                        
                        cdcsplit[0] = new ContextDataCollection(allData.get(cb));
                        cdcsplit[1] = cdcsplit[0].split(si.splitc.getContextID(), si.splitc.getBucketID());
                    // make boxes smaller. 
//                        System.out.println("Before: 0: " + boxes[0] + " 1: " + boxes[1]);
                        boxes[0] = ContextCharacteristicsBox.findSmallestEnclosingBox(cdcsplit[0]);
                        boxes[1] = ContextCharacteristicsBox.findSmallestEnclosingBox(cdcsplit[1]);
  //                      System.out.println("After: 0: " + boxes[0] + " 1: " + boxes[1]);
*/
                        boxes[0] = ContextCharacteristicsBox.findSmallestEnclosingBox(currnode.getLeftChild().getData());
                        boxes[1] = ContextCharacteristicsBox.findSmallestEnclosingBox(currnode.getRightChild().getData());

                    buildOptimalTree(boxes[0],currnode.getLeftChild());              
                    buildOptimalTree(boxes[1],currnode.getRightChild());                                  
                }
        }

}
